package com.da.javatest.niuke.baodian;

import java.util.ArrayList;
import java.util.List;

import com.da.javatest.niuke.common.ListNode;
import com.da.javatest.niuke.common.TreeNode;

/**
 * @author chenlida
 * @date 2020/10/7 13:32
 * https://www.nowcoder.com/practice/cb6c883b123b44399377d0c71e6ba3ea?tpId=8&tags=&title=&diffculty=0&judgeStatus=0&rp=1
 */
public class C21TreeLevel {
    private List<Integer> list = new ArrayList<>();

    public ListNode getTreeLevel(TreeNode root, int dep) {
        if (root == null) {
            return null;
        }
        if (dep == 1) {
            return new ListNode(root.val);
        }
        search(root, 1, dep);
        return buildListNode();
    }

    // 二叉树前序遍历
    private void search(TreeNode root, int level, int dep) {
        if (root != null) {
            if (level == dep) {
                list.add(root.val);
                return;
            }
            search(root.left, level + 1, dep);
            search(root.right, level + 1, dep);
        }
    }

    private ListNode buildListNode() {
        ListNode head = new ListNode(-1);
        ListNode p = head;
        for (Integer integer : list) {
            p.next = new ListNode(integer);
            p = p.next;
        }
        return head.next;
    }


    ListNode in = new ListNode(-1);
    ListNode p = in;
    public ListNode getTreeLevel2(TreeNode root, int dep) {
        if (root == null || dep <= 0) {
            return null;
        }
        if (dep == 1) {
            p.next = new ListNode(root.val);
            p = p.next;
        } else {
            getTreeLevel2(root.left, dep - 1);
            getTreeLevel2(root.right, dep - 1);
        }
        return in.next;

    }

}
